「唯一生き残るのは、変化できる者である！ 生物進化の原理に基づいた最適化手法の 遺伝的アルゴリズムのご紹介」というタイトルで DevelopersIO 2023 に登壇しました！ #devio2023

こんにちは、CX 事業本部のジョン・ヒョンジェです。

2023 年 7/7 ~ 7/8 に DevelopersIO 2023 が開催されました。とても多くのセッションがありましたが、私も「唯一生き残るのは、変化できる者である！生物進化の原理に基づいた最適化手法の遺伝的アルゴリズムのご紹介」というタイトルでサブセッションに登壇することができました！

セッションの概要

登壇者

クラスメソッド CX事業本部 Delivery部 サーバーサイドエンジニア ジョン・ヒョンジェ

タイトル

唯一生き残るのは、変化できる者である！ 生物進化の原理に基づいた最適化手法の 遺伝的アルゴリズムのご紹介

概要

チャールズ・ダーウィンの進化論を知っていますか？遺伝的アルゴリズムはこの生物進化論をもとにして、生物が環境に適応し進化していく様子を模倣した最適化手法の一つです。このセッションでは、この遺伝的アルゴリズムがどうやって自ら学習をし、最適解を探すのかについてご紹介します

資料

デモのコード共有

このセッションでは「遺伝的アルゴリズムを利用して、サッカーのペナルティーキックで飛んでくるシュートを全部防げるゴールキーパーを誕生させる」という簡単なデモを行いましたが、このデモで使った Python のコードを共有します。

from random import randint

# 最初世代の染色体はランダムな遺伝子情報を持つ
# ex) [[1,0,3,2,3,4],[4,2,4,0,1,2],[0,2,3,1,4,5], ....]
def makeKeepersGene():
  keepersGene = []

  for i in range(keepers_num):
    gene = []
    for i in range(genes_num):
      gene.append(randint(0,5))
    keepersGene.append(gene)

  return keepersGene

# 適応度関数
# 実際、染色体を問題に適応して、評価する
def startPenealtyKick(keepersGene):
  scores = []

  # ex) キックの方向が3の場合、キーパーは遺伝子情報のインデックス3の値に該当する方向に防ぎに行く
  # もし、遺伝子情報のインデックス3の値が3だったら、成功でスコア１獲得。他の値だったら、失敗でスコア獲得できない
  # 20点満点
  for keeperGene in keepersGene:
    score = 0
    for i in range(kickers_num):
      kick = randint(0,5)
      if(keeperGene[kick] == kick):
        score += 1
    scores.append(score)

  return scores

# 優秀な染色体を選択する
def rankKeeper(scores):
  first = 0
  second = 0

  # スコアが一番高い1位、2位を選択し、そのインデックスを返却する
  for i in range(len(scores)):
    if scores[i] > scores[first]:
      first = i

  if first == 0:
    second = 1

  for i in range(len(scores)):
    if scores[i] > scores[second]:
      if i != first:
        second = i

  return [first, second]

# 選択された染色体の遺伝子情報を交差して、子孫を生成する
def makeNewGenerationKeepers(firstKeeper, secondKeeper):
  keepersGene = []

  # CrossOver
  # 1位、2位の染色体の遺伝子をランダムに交差する
  for i in range(keepers_num):
    gene = []
    for j in range(genes_num):
      # 一様交差
      randomNum = randint(1,2)
      if(randomNum == 1):
        gene.append(firstKeeper[j])
      else:
        gene.append(secondKeeper[j])
    keepersGene.append(gene)

  newGenerationKeepers = makeMutationKeeper(keepersGene)

  return newGenerationKeepers

# 突然変異生成
def makeMutationKeeper(keepersGene):
  # 後ろ二つの染色体の遺伝子の一部をランダムな値に再設定する
  keepersGene[keepers_num - 1][randint(0,5)] = randint(0,5)
  keepersGene[keepers_num -2][randint(0,5)] = randint(0,5)

  return keepersGene


# 実行する世代数
generation = 100
# 染色体数
keepers_num = 10
# ペナルティーキック実行数(問題に適用する回数)
kickers_num = 20
# 各染色体の遺伝子数
genes_num = 6
# 染色体の情報
Genes = []

for generation in range(1, generation + 1):
  print(str(generation) + '世代')

  # 最初世代の染色体の遺伝子情報を生成する
  if generation == 1:
    Genes = makeKeepersGene()
  print('キーパーの遺伝子情報: ', Genes)

  # ペナルティーキックを実行し、評価する
  scores = startPenealtyKick(Genes)
  print("スコア: ", scores)

  # 評価結果、1位と2位の染色体を選択
  rankerKeepers = rankKeeper(scores)
  firstKeeper = Genes[rankerKeepers[0]]
  secondKeeper = Genes[rankerKeepers[1]]
  print("1位のキーパーの遺伝時: ", firstKeeper)
  print("2位のキーパーの遺伝時: ", secondKeeper)

  # 1位、2位の染色体の遺伝子情報を交差・突然変異生成をして、次世代の染色体作成（世代交代）
  Genes = makeNewGenerationKeepers(firstKeeper, secondKeeper)

このコードを実行して、出力されるログをみると

1世代
キーパーの遺伝子情報:  [[1, 4, 5, 5, 2, 4], [2, 3, 1, 4, 1, 5], [4, 0, 0, 1, 5, 5], [2, 4, 4, 1, 1, 0], [5, 1, 3, 3, 0, 3], [1, 0, 2, 5, 3, 2], [4, 1, 0, 0, 1, 0], [2, 1, 0, 2, 1, 4], [3, 5, 5, 4, 2, 0], [4, 4, 5, 1, 5, 3]]
スコア:  [0, 3, 2, 0, 7, 1, 2, 3, 0, 0]
1位のキーパーの遺伝時:  [5, 1, 3, 3, 0, 3]
2位のキーパーの遺伝時:  [2, 3, 1, 4, 1, 5]
.
.
.
10世代
キーパーの遺伝子情報:  [[2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5], [2, 1, 3, 3, 1, 5]]
スコア:  [11, 11, 12, 4, 9, 9, 13, 7, 10, 10]
1位のキーパーの遺伝時:  [2, 1, 3, 3, 1, 5]
2位のキーパーの遺伝時:  [2, 1, 3, 3, 1, 5]
.
.
.
20世代
キーパーの遺伝子情報:  [[1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 1, 3, 3, 4, 5], [1, 3, 3, 3, 4, 5]]
スコア:  [14, 17, 16, 9, 13, 16, 15, 11, 15, 7]
1位のキーパーの遺伝時:  [1, 1, 3, 3, 4, 5]
2位のキーパーの遺伝時:  [1, 1, 3, 3, 4, 5]
.
.
.
100世代
キーパーの遺伝子情報:  [[0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5], [0, 1, 4, 3, 4, 5], [0, 1, 2, 3, 4, 5]]
スコア:  [20, 20, 20, 20, 20, 20, 20, 20, 13, 20]
1位のキーパーの遺伝時:  [0, 1, 2, 3, 4, 5]
2位のキーパーの遺伝時:  [0, 1, 2, 3, 4, 5]

のように、染色体がだんだん進化していて、100世代には飛んでくるシュートを全部防げるゴールキーパー(染色体)が誕生される結果を確認することができます。

終わりに

このセッションでは遺伝的アルゴリズムの概要、原理などの説明と簡単なデモも行いました。このブログで共有したデモのコードを利用して、色々条件や演算方式、突然変異の比率などを変えながら、染色体の進化にどういうふうに影響を与えるかを試してみるのも遺伝的アルゴリズムを理解するにはとてもいいと思います。

以前、執筆した以下のブログでも遺伝的アルゴリズムについて書いているので、こちらもご参考してください！では、以上です。ありがとうございます。